home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / hlbsp / merge.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2002-02-25  |  6.9 KB  |  260 lines
  1. #include "bsp5.h"
  2.  
  3. //  TryMerge
  4. //  MergeFaceToList
  5. //  FreeMergeListScraps
  6. //  MergePlaneFaces
  7. //  MergeAll
  8.  
  9. #define CONTINUOUS_EPSILON    ON_EPSILON
  10.  
  11. // =====================================================================================
  12. //  TryMerge
  13. //      If two polygons share a common edge and the edges that meet at the
  14. //      common points are both inside the other polygons, merge them
  15. //      Returns NULL if the faces couldn't be merged, or the new face.
  16. //      The originals will NOT be freed.
  17. // =====================================================================================
  18. static face_t*  TryMerge(face_t* f1, face_t* f2)
  19. {
  20.     vec_t*          p1;
  21.     vec_t*          p2;
  22.     vec_t*          p3;
  23.     vec_t*          p4;
  24.     vec_t*          back;
  25.     face_t*         newf;
  26.     int             i;
  27.     int             j;
  28.     int             k;
  29.     int             l;
  30.     vec3_t          normal;
  31.     vec3_t          delta;
  32.     vec3_t          planenormal;
  33.     vec_t           dot;
  34.     dplane_t*       plane;
  35.     bool            keep1;
  36.     bool            keep2;
  37.  
  38.     if (f1->numpoints == -1 || f2->numpoints == -1)
  39.     {
  40.         return NULL;
  41.     }    
  42.     if (f1->texturenum != f2->texturenum)
  43.     {
  44.         return NULL;
  45.     }
  46.     if (f1->contents != f2->contents)
  47.     {
  48.         return NULL;
  49.     }
  50.  
  51.     //
  52.     // find a common edge
  53.     //      
  54.     p1 = p2 = NULL;                                        // shut up the compiler
  55.     j = 0;
  56.  
  57.     for (i = 0; i < f1->numpoints; i++)
  58.     {
  59.         p1 = f1->pts[i];
  60.         p2 = f1->pts[(i + 1) % f1->numpoints];
  61.         for (j = 0; j < f2->numpoints; j++)
  62.         {
  63.             p3 = f2->pts[j];
  64.             p4 = f2->pts[(j + 1) % f2->numpoints];
  65.             for (k = 0; k < 3; k++)
  66.             {
  67.                 if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
  68.                 {
  69.                     break;
  70.                 }
  71.                 if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
  72.                 {
  73.                     break;
  74.                 }
  75.             }
  76.             if (k == 3)
  77.             {
  78.                 break;
  79.             }
  80.         }
  81.         if (j < f2->numpoints)
  82.         {
  83.             break;
  84.         }
  85.     }
  86.  
  87.     if (i == f1->numpoints)
  88.     {
  89.         return NULL;                                       // no matching edges
  90.     }
  91.  
  92.     //
  93.     // check slope of connected lines
  94.     // if the slopes are colinear, the point can be removed
  95.     //
  96.     plane = &g_dplanes[f1->planenum];
  97.     VectorCopy(plane->normal, planenormal);
  98.  
  99.     back = f1->pts[(i + f1->numpoints - 1) % f1->numpoints];
  100.     VectorSubtract(p1, back, delta);
  101.     CrossProduct(planenormal, delta, normal);
  102.     VectorNormalize(normal);
  103.  
  104.     back = f2->pts[(j + 2) % f2->numpoints];
  105.     VectorSubtract(back, p1, delta);
  106.     dot = DotProduct(delta, normal);
  107.     if (dot > CONTINUOUS_EPSILON)
  108.     {
  109.         return NULL;                                       // not a convex polygon
  110.     }
  111.     keep1 = dot < -CONTINUOUS_EPSILON;
  112.  
  113.     back = f1->pts[(i + 2) % f1->numpoints];
  114.     VectorSubtract(back, p2, delta);
  115.     CrossProduct(planenormal, delta, normal);
  116.     VectorNormalize(normal);
  117.  
  118.     back = f2->pts[(j + f2->numpoints - 1) % f2->numpoints];
  119.     VectorSubtract(back, p2, delta);
  120.     dot = DotProduct(delta, normal);
  121.     if (dot > CONTINUOUS_EPSILON)
  122.     {
  123.         return NULL;                                       // not a convex polygon
  124.     }
  125.     keep2 = dot < -CONTINUOUS_EPSILON;
  126.  
  127.     //
  128.     // build the new polygon
  129.     //
  130.     if (f1->numpoints + f2->numpoints > MAXEDGES)
  131.     {
  132.         //              Error ("TryMerge: too many edges!");
  133.         return NULL;
  134.     }
  135.  
  136.     newf = NewFaceFromFace(f1);
  137.  
  138.     // copy first polygon
  139.     for (k = (i + 1) % f1->numpoints; k != i; k = (k + 1) % f1->numpoints)
  140.     {
  141.         if (k == (i + 1) % f1->numpoints && !keep2)
  142.         {
  143.             continue;
  144.         }
  145.  
  146.         VectorCopy(f1->pts[k], newf->pts[newf->numpoints]);
  147.         newf->numpoints++;
  148.     }
  149.  
  150.     // copy second polygon
  151.     for (l = (j + 1) % f2->numpoints; l != j; l = (l + 1) % f2->numpoints)
  152.     {
  153.         if (l == (j + 1) % f2->numpoints && !keep1)
  154.         {
  155.             continue;
  156.         }
  157.         VectorCopy(f2->pts[l], newf->pts[newf->numpoints]);
  158.         newf->numpoints++;
  159.     }
  160.  
  161.     return newf;
  162. }
  163.  
  164. // =====================================================================================
  165. //  MergeFaceToList
  166. // =====================================================================================
  167. static face_t*  MergeFaceToList(face_t* face, face_t* list)
  168. {
  169.     face_t*         newf;
  170.     face_t*         f;
  171.  
  172.     for (f = list; f; f = f->next)
  173.     {
  174.         //CheckColinear (f);            
  175.         newf = TryMerge(face, f);
  176.         if (!newf)
  177.         {
  178.             continue;
  179.         }
  180.         FreeFace(face);
  181.         f->numpoints = -1;                                 // merged out
  182.         return MergeFaceToList(newf, list);
  183.     }
  184.  
  185.     // didn't merge, so add at start
  186.     face->next = list;
  187.     return face;
  188. }
  189.  
  190. // =====================================================================================
  191. //  FreeMergeListScraps
  192. // =====================================================================================
  193. static face_t*  FreeMergeListScraps(face_t* merged)
  194. {
  195.     face_t*         head;
  196.     face_t*         next;
  197.  
  198.     head = NULL;
  199.     for (; merged; merged = next)
  200.     {
  201.         next = merged->next;
  202.         if (merged->numpoints == -1)
  203.         {
  204.             FreeFace(merged);
  205.         }
  206.         else
  207.         {
  208.             merged->next = head;
  209.             head = merged;
  210.         }
  211.     }
  212.  
  213.     return head;
  214. }
  215.  
  216. // =====================================================================================
  217. //  MergePlaneFaces
  218. // =====================================================================================
  219. void            MergePlaneFaces(surface_t* plane)
  220. {
  221.     face_t*         f1;
  222.     face_t*         next;
  223.     face_t*         merged;
  224.  
  225.     merged = NULL;
  226.  
  227.     for (f1 = plane->faces; f1; f1 = next)
  228.     {
  229.         next = f1->next;
  230.         merged = MergeFaceToList(f1, merged);
  231.     }
  232.  
  233.     // chain all of the non-empty faces to the plane
  234.     plane->faces = FreeMergeListScraps(merged);
  235. }
  236.  
  237. // =====================================================================================
  238. //  MergeAll
  239. // =====================================================================================
  240. void            MergeAll(surface_t* surfhead)
  241. {
  242.     surface_t*      surf;
  243.     int             mergefaces;
  244.     face_t*         f;
  245.  
  246.     Verbose("---- MergeAll ----\n");
  247.  
  248.     mergefaces = 0;
  249.     for (surf = surfhead; surf; surf = surf->next)
  250.     {
  251.         MergePlaneFaces(surf);
  252.         for (f = surf->faces; f; f = f->next)
  253.         {
  254.             mergefaces++;
  255.         }
  256.     }
  257.  
  258.     Verbose("%i mergefaces\n", mergefaces);
  259. }
  260.